package net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithms

import scalax.collection.immutable.Graph
import net.cyndeline.rldungeon.dgs.graph.Room
import net.cyndeline.rldungeon.dgs.strategy.help.{CollapsedEdge, CollapsedNode}

/**
 * For dependency injection.
 */
trait EdgeTrimmer {
  def removeVertices[VType <: Room[VType]](graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]): Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]
}

/**
 * Removes the outermost pointless nodes on each branch of a tree that cannot hold rewards or activators.
 * The algorithm terminates when every such branch has a node on its edge that is both pointless and can
 * hold rewards/activators, or a non-pointless node, or has been removed entirely.
 */
class CollapsedGraphEdgeTrimmer extends EdgeTrimmer {

  /**
   * Repeatedly finds a pointless node with degree 1 that cannot hold additional rewards or activators. When such a
   * vertex is found, the edge is traversed inwards until a pointless node that can hold rewards are found, or a
   * non-pointless node (belonging to the main path), or a node that has degree > 2. When this happens, every node
   * up until the found node is removed.
   *
   * The worst case runtime is 2 * (sum(i), i = 0 to n) * v, where n is the amount of nodes outside the main path,
   * and v is the amount of vertices represented by the 'i collapsed nodes. This occurs when the pointless areas form
   * a balanced binary tree and every node apart from the main path is both pointless and cannot hold rewards.
   * @param graph Graph to trim edges of.
   * @return A graph where every edge-node (degree 1) is either non-pointless, or pointless and able to carry rewards.
   */
  def removeVertices[VType <: Room[VType]](graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]): Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = {
    var currentGraph = graph
    var pointlessEdgeNodeThatCannotHoldRewards: Option[CollapsedNode[VType]] = findFullEdgeNode(currentGraph)

    while (pointlessEdgeNodeThatCannotHoldRewards.isDefined) {
      val n = pointlessEdgeNodeThatCannotHoldRewards.get
      val removableNodes = findNodesToRemove(n, currentGraph)

      val it = removableNodes.iterator
      while (it.hasNext) {
        val nodeToRemove = it.next()
        currentGraph -= nodeToRemove
      }

      pointlessEdgeNodeThatCannotHoldRewards = findFullEdgeNode(currentGraph)
    }

    currentGraph
  }

  /**
   * Finds a node at the edge of a branch that cannot hold rewards.
   * @param graph Graph with the node set to search.
   * @return A pointless node of degree 1 that cannot hold rewards, or None if no such node exists.
   */
  private def findFullEdgeNode[VType <: Room[VType]](graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]): Option[CollapsedNode[VType]] = {
    val inner = graph.nodes.find(n => {
      if (n.degree <= 1) {
        n.isPointless && !n.canHoldRewards
      } else {
        false
      }
    })

    if (inner.isDefined) {
      val outer: CollapsedNode[VType] = inner.get
      Option(outer)
    } else {
      None
    }
  }

  /**
   * Follows a path inwards from an edge node until a node that is either not pointless, or can have rewards, or
   * is in the center of an intersection that may lead to other pointless nodes is found.
   *
   * This has to be done in a method of its own since the scala compiler complains about type incompatibility
   * when traversing in a method call having multiple graph instances of the same type.
   *
   * @param node Node to start traversing from.
   * @param graph Graph to traverse.
   * @return All traversed nodes that doesn't match the above properties that can be reached from the initial node
   *         without passing a node with matching properties..
   */
  private def findNodesToRemove[VType <: Room[VType]](node: CollapsedNode[VType], graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]): Set[CollapsedNode[VType]] = {
    val inner = graph.get(node)
    var nodes = Set[CollapsedNode[VType]]()

    def addToNodes(n: graph.NodeT) {
      nodes += n
    }

    inner.withSubgraph(n => n.isPointless && !n.canHoldRewards && n.degree <= 2).foreach(addToNodes)
    nodes
  }

}
